package com.suanfa.sort;

import com.suanfa.util.ArrayUtils;

/**
 * 堆排序
 * 1、构造堆二叉树，父节点和子节点有序， 左右节点无序
 * i 左子树 2*i+1 右子树 2*i+2  最小非叶子节点 length/2-1
 * 2、根节点和最后一个节点交换之后，再次调整  复杂度 O(nlgn)
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] arr={ 49, 38, 65, 97, 23,  22, 76, 1, 5, 8, 2, 0, -1, 22};
        f1(arr);
        ArrayUtils.printArray(arr);
    }

    public static void heapSort(int[] arr){

        //调整大顶堆
        int start = arr.length/2 -1;//最后一个非叶子节点
        //从最后一个非叶子节点开始调整,构建二叉树
        for(int i = start; i >=0; i--){
             adjustHeap(arr, i, arr.length);
        }
        //首位元素交换，每次从第一个元素开始重新调整，
        // 经过构建堆找到了最大值，将最大值和最后一个值交换，，将最大值放到最后之后，不在参与排序
        for(int i= arr.length - 1; i > 0; i--){
            ArrayUtils.swap(arr, 0, i);
            adjustHeap(arr, 0, i);//左右子树比对找到最大值 交换输出
        }
    }

    public static void adjustHeap(int[] arr, int index, int length){
        int left = index * 2 + 1;
        int right = index * 2 + 2;
        int largest = index;
        if(left < length && arr[left] > arr[index]){
            largest = left;
        }

        if(right < length && arr[right] > arr[left]){
            largest = right;
        }

        if(largest != index){
            ArrayUtils.swap(arr, largest, index);
            adjustHeap(arr, largest, length);
        }

    }

    public static void f1(int[] arr){
        int index = arr.length / 2 - 1;//根节点
        for(int i = index; i>=0; i--){
            f2(arr, i, arr.length);
        }
        for(int i= arr.length -1; i>=0; i--){
            swap(arr, 0, i);
            f2(arr, 0,i);
        }




    }
    public static void f2(int[] arr, int index, int length){
            int left = 2*index + 1;
            int right = 2*index +2;
            int largest = index;
            if(left < length && arr[left]> arr[largest]){
                largest = left;
            }
            if(right < length && arr[right] > arr[largest]){
                largest = right;
            }
            if(largest != index){
                swap(arr, index, largest);
                f2(arr, largest, length);
            }

    }
    public static void swap(int[] arr, int i1, int i2){
        if(i1 != i2){
            int v1 = arr[i1];
            arr[i1] = arr[i2];
            arr[i2] = v1;
        }
    }


}
